package com.shigi.knapsack.solvers;

import com.shigi.knapsack.KnapsackInstance;
import com.shigi.knapsack.KnapsackItem;
import com.shigi.knapsack.KnapsackSolution;
import com.shigi.knapsack.KnapsackSolver;

/**
 * Created by Miroslav Šiagi on 02/11/14.
 */
public class DynamicProgrammingWeight implements KnapsackSolver {

    private KnapsackSolution knapsackSolution;
    private KnapsackInstance knapsackInstance;
    private KnapsackItem[] knapsackItems;

    public KnapsackSolution solve(KnapsackInstance knapsackInstance) {
        this.knapsackInstance = knapsackInstance;
        this.knapsackSolution = new KnapsackSolution(knapsackInstance.getId());
        this.knapsackSolution.setNumberOfItems(knapsackInstance.getNumberOfItems());
        this.knapsackItems = this.knapsackInstance.getKnapsackItems();
        int numberOfItems = this.knapsackItems.length;

        int[] values = new int[numberOfItems];
        int[] weights = new int[numberOfItems];

        for (int i = 0; i < numberOfItems; i++) {
            values[i] = this.knapsackItems[i].getValue();
            weights[i] = this.knapsackItems[i].getWeight();
        }
        createSolution(values, weights);

        this.knapsackSolution.setNumberOfItems(this.knapsackItems.length);
        return this.knapsackSolution;
    }

    private void createSolution(int[] values, int[] weights) {
        int numberOfItems = this.knapsackItems.length;
        int maxWeight = this.knapsackInstance.getTotalWeight();
        int optValue = 0;

        int[] profit = new int[numberOfItems+1];
        int[] weight = new int[numberOfItems+1];

        for (int n = 1; n <= numberOfItems; n++) {
            profit[n] = values[n-1];
            weight[n] = weights[n-1];
        }

        // opt[n][w] = max profit of packing items 1..n with weight limit w
        // sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n?
        int[][] opt = new int[numberOfItems+1][maxWeight+1];
        boolean[][] sol = new boolean[numberOfItems+1][maxWeight+1];

        for (int i_n = 1; i_n <= numberOfItems; i_n++) {
            for (int i_w = 1; i_w <= numberOfItems; i_w++) {

                // don't take item n
                int option1 = opt[i_n-1][i_w];

                // take item n
                int option2 = Integer.MIN_VALUE;
                if (weight[i_n] <= i_w) option2 = profit[i_n] + opt[i_n-1][i_w-weight[i_n]];

                // select better of two options
                opt[i_n][i_w] = Math.max(option1, option2);
                sol[i_n][i_w] = (option2 > option1);
            }
        }

        // determine which items to take
        boolean[] take = new boolean[numberOfItems+1];
        for (int n = numberOfItems, w = maxWeight; n > 0; n--) {
            if (sol[n][w]) {
                take[n] = true;
                w = w - weight[n];
                optValue += profit[n];
            } else {
                take[n] = false;
            }
        }

        this.knapsackSolution.setTotalValue(optValue);
    }
}
